The present invention relates to a main storage managing method for computer systems and, more particularly, to a virtual storage managing method suited to use in a system in which a program requiring a high response speed and a program requiring a large storage capacity are executed simultaneously.
Hitherto, as one of the most high-grade managing systems in the main storage management of computer systems, a virtual storage called ON-DEMAND PAGE SWAPPING (abbreviation DEMAND PAGING) has been known. An example of such a system is shown in S. E. Mandick & Donovan: Operating Systems, pp 139-165; McGraw Hill Book Company, 1974.
A virtual memory managing system is characterized in that the address of the memory device is not the real address (or physical address) imparted to the physical main storage but is identified by a virtual address attached to a virtual storage region which does not actually exist and is constituted solely of a logical construction. It is, therefore, essential to employ hardware for obtaining the correspondence between the virtual address and the real address as well as a software program for this purpose. The hardware and the software for obtaining this correspondence in combination are usually called in address translation mechanism. The aforementioned DEMAND PAGING is one of the examples of a measure for realizing such an address translation mechanism. The DEMAND PAGING METHOD, therefore, will be outlined hereinbelow.
According to the demand paging method, the virtual storage region is beforehand sectioned into a plurality of small regions of a fixed length referred to as a "Page". On the other hand, the main memory is beforehand divided into small regions of the same length as the page and referred to as Page Frames (abbreviation PF, hereinunder). The pages and PF are provided with Nos. starting from 0 (zero), respectively. The program is so arranged on one or a plurality of consecutive pages in such a manner as not to lap the pages carrying other programs. The following procedure is taken in the DEMAND PAGE METHOD for executing the program. During execution of a program, when it proves that a reference is made to a virtual address in the page which is not correlated to the PF (this will be referred to as "page fault"), an operation is made to obtain correspondence between the page and the PF.
Namely, the aforementioned address translation mechanism operates to establish correpondence between the page and the PF which has not been correlated to the page (such PF will be referred to as "empty" PF). When there is no empty PF, the correspondence between another page and PF is dismissed to make an empty PF and this new empty PF is made to correspond to the aforementioned page.
After the completion of execution of the program, all of the pages employed by the program are dismissed from the correspondence to the PFs so that the PFs become empty.
This DEMAND PAGE METHOD offers the following advantages.
(1) Since only the pages under execution have to be made to correspond to a PF, the size of the program is not limited by the capacity of the main storage. Namely, there is no limit in the size of the virtual storage region theoretically.
(2) There is no tendency that the pages for reference and execution in a predetermined time length are concentrated only in a portion of the program region, so that it seldom occurs that the page which is executed undesirably occupies the PF. In consequence, the efficiency of use of the main storage is considerably high.
(3) For these reasons, when a plurality of programs are executed simultaneously (referred to as "multiprogramming"), the total number of pages employed can be made much smaller as compared with the total number of pages of the program group.
As a consequence, the number of programs which can be contained by the main storage device is much greater than the number which is given by the total page number. This conveniently permits a degree of the multiplication of programs.
On the other hand, however, this method suffers from the following problems.
(1) Since the page fault occurs at a certain frequency during execution of the program, the original program execution time is shortened by the time length for executing the substitution algorithm (this time length will be referred to as the "overhead of the OS"), resulting in a deteriorated processing performance.
(2) Since there is no means for forecasting this reduction in the processing performance in advance, if many programs are executed in a random manner, the undesirable phenomenon called "Thrashing" takes place in which a large part of the working time of the computer is consumed for the overhead of the OS, so that the computer system may materially fail to function.
(3) The price of the computer system is raised by the addition of the address translation mechanism.
Among these three problems, the third one is not so serious because the address translation mechanism can be nowadays produced at a sufficiently low cost thanks to the current development in the technology concerning hardware devices. The first and second problems, however, are fundamental ones and are serious particularly when the real time processing such as in plant control systems is conducted.